An adder is a digital circuit that performs addition of numbers. The most common adders operate on binary numbers. Binary numbers represent numeric values using only two different symbols: 0 and 1. Each digit of a binary number represents an increasing power of 2, with the rightmost digit representing 20, the next representing 21, then 22, and so on. The value of a binary number can be calculated by Equation 1:X×20+Y×21+Z×22  Equation 1
where X, Y, Z etc. can have the value of 0 or 1.
Adding two single-digit binary numbers A and B is relatively simple. The sum of A+B is S and CY, where sum S is equal to X in Equation 1 and CY, which is a “carry bit”, is equal to Y in Equation 1.
Thus, the four possible ways to add two one-bit numbers A and B produce:
(a) 0+0→S=0, CY=0
(b) 0+1→S=1, CY=0
(c) 1+0→S+1, CY=0
(d) 1+1→S=0, CY=1
In many computers and other kinds of processors, adders are used not only in the arithmetic logic units, but also in other parts of the processor, where they are used to calculate addresses, table indices, increment and decrement operators, and similar operations.
FIG. 1 to which reference is now made illustrates a one-bit half adder 100, a one-bit full adder 110 and a multi-bit adder 120, all known in the art.
One bit half adder 100, known in the art, adds two single binary digits A and B and has two outputs, a sum S and a carry CYout. The carry represents an overflow into the next digit of a multi-digit addition.
A full adder 110, adds binary numbers and accounts for values carried in as well as those carried out. One-bit full adder 110 adds three one-bit numbers, A, B, and CYin, where A and B are the bits to add and CYin is a bit carried in from a previous one bit full adder operation. The output of the full adder is S and CYout where S is the calculated sum of the three input bits and (Tout is a bit carried out.
Multi-bit adder 120, is constructed from multiple one-bit full adders to add two N-bit numbers P and Q. Each full adder input, in addition to a bit A from P and a bit B from Q, receives an input carry bit CYin, which is the output carry bit CYout of the previous adder. Note that the first (and only the first) full adder always has a zero valued carry in bit CYin=0 as there is no carry in from a previous step. The example of multi-bit adder 120 is a four bit adder and is constructed from four one bit adders 110 connected such that the carry out of one adder is the carry in of the next adder. The output of multi-bit adder 120 is a multi-bit number R constructed from the resulting bits S of each full adder 110 and the CYout of the last (leftmost) full adder.
FIG. 2, to which reference is now made, is the truth table 200 of a one bit full adder. Each row in table 200 provides a possible permutation of input values for each of the input bits A, B, and CYin. Table 200 also lists the expected output S, which is the result of the sum A+B+CYin, and the carry out bit CYout which is the output carry of the sum operation for each permutation.
In line 210, the values of the input bits are A=0, B=0, and CYin=0. The resulting binary sum is 0 (0+0+0) and, thus the value of S is 0 and the value of CYout is 0. In lines 220, 230 and 250 the value of one of the input bits is 1 and the value of the two other bits is 0. The resulting binary sum is 1 and therefore, the value of S is 1 and of CYout is 0. In lines 240, 260, and 270 the value of one of the bits is 0 and the value of the two other bits is 1. The binary sum (1+1+0) is 10, where the sum S is 0 and carry out CYout is 1. In line 280 the value of all the input bits is 1 so the result is 11 (1+1+1) and therefore the value of S is 1 and of CYout is 1.
The full adder can be implemented by many digital circuits, having many combinations of logic gates. A full adder has also been implemented within an in-memory computation device, described in U.S. patent application Ser. No. 15/146,908 filed on May 5, 2016, and assigned to the common assignee of the present application. U.S. patent application Ser. No. 15/146,908 is incorporated herein by reference. The associative computation of the full adder described in U.S. patent application Ser. No. 15/146,908 takes 12 clock cycles.